<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>

</body>
<script>
    function MyNodeList() {
        this.head = null;
        this.length = 0;

        var Node = function (val) {
            this.val = val;
            this.next = null;
        }

        MyNodeList.prototype.append = function (val) {
            let node = new Node(val);
            if (this.head === null) {
                this.head = node;
            } else {
                let node1 = this.head;
                // 遍历，将node1变成最后一个节点
                while (node1.next) {
                    node1 = node1.next
                }
                node1.next = node;
            }
            this.length++;
        }
        MyNodeList.prototype.removeAt = function (index) {
            if (index >= this.length) return null;

            let node1 = this.head;
            // 将node1变成要删除的节点的上一个节点
            for (let i = 0; i < index - 1; i++) {
                node1 = node1.next
            }
            let elem = node1.next.val
            node1.next = node1.next.next
            this.length--
            return elem
        }
        MyNodeList.prototype.remove = function (elem) {
            let node1 = this.head;
            let index = 0;
            if (node1.val = elem) {
                this.head = node1.next;
                return index;
            }
            while (node1) {
                index++;
                if (node1.next.val === elem) {
                    node1.next = node1.next.next
                    this.length--
                    return index
                }
                node1 = node1.next;
            }
            return -1
        }
        MyNodeList.prototype.insert = function (elem, index) {
            var node = new Node(elem);
            let node1 = this.head;
            for (let i = 0; i < index - 1; i++) {
                node1 = node1.next;
            }
            node.next = node1.next;
            node1.next = node
            this.length++
        }
        MyNodeList.prototype.get = function (index) {
            if (index >= this.length) return null;
            let node1 = this.head;
            for (let i = 0; i < index; i++) {
                node1 = node1.next
            }
            return node1.val
        }
        MyNodeList.prototype.reverse = function () {
            let node1 = this.head;
            let prev = null;
            while (node1) {
                const next = node1.next;
                node1.next = prev;
                prev = node1;
                node1 = next;
            }
            this.head = prev
            return prev
        }
        MyNodeList.prototype.isEmpty = function (val) {
            return this.head = null ? true : false;
        }
        MyNodeList.prototype.toString = function () {
            let node1 = this.head;
            let arr = [];
            while (node1) {
                arr.push(node1.val)
                node1 = node1.next
            }
            return arr
        }
        MyNodeList.prototype.size = function () {
            let n = 0;
            let node = this.head;
            if (!node) return n;
            while (node.next) {
                node = node.next
                n++;
            }
            return n + 1
        }
        MyNodeList.prototype.getKthFromEnd = function (k) {
            var fast = this.head;
            var slow = this.head;
            let n = 0;
            while (fast) {
                fast = fast.next;
                if (n >= k) {
                    slow = slow.next;
                }
                n++;
            }
            return slow
        }
    }

    var listNode = new MyNodeList();
    listNode.append(1);
    listNode.append(2);
    listNode.append(3);
    listNode.append(4);
    // console.log(listNode.removeAt(3));
    // console.log(listNode.get(2));
    console.log(listNode.reverse());
    console.log(listNode.getKthFromEnd(2));
    console.log(listNode.size());
    console.log(listNode.toString());



    /* 
    单向链表
    append(element)  向链表的尾部插入一个节点
    insert(position,element)  向链表的指定位置插入一个节点 位置按照0,1,2,3,4,...
    get(position)  获取对应位置的元素
    indexOf(element)  返回元素在列表中的索引  如果没有则返回-1
    update(element,position)  修改某个位置的元素
    removeAt(position) 按照指定位置删除一个节点  return 被删除的节点的element
    remove(element)  按照指定元素删除一个节点  return 被删除的节点在链表中的位置
    isEmpty() 如果链表没有元素 return true  否则  return false
    size()  返回链表中节点个数
    toString() return 链表中的所有元素
*/
    function LinkedList_oneWay() {
        this.head = null
        this.length = 0

        function Node(element, next = null) {
            this.element = element
            this.next = next
        }

        LinkedList_oneWay.prototype.append = function (element) {
            let node = new Node(element)

            if (this.head === null) {
                // 如果该节点是第一个节点
                this.head = node
            } else {
                let node1 = this.head

                // 遍历到最后一项  不包括最后一项
                while (node1.next !== null) {
                    node1 = node1.next
                }
                node1.next = node
            }
            this.length++
        }

        LinkedList_oneWay.prototype.insert = function (element, position) {

            // 1. 新建节点
            let node = new Node(element)

            // 2. 插入到指定位置
            let node1 = this.head
            for (let i = 0; i < position - 1; i++) {
                node1 = node1.next
            }
            node.next = node1.next
            node1.next = node

            this.length++
        }

        LinkedList_oneWay.prototype.get = function (position) {
            if (position >= this.length) {
                return null
            }

            let node1 = this.head
            for (let i = 0; i < position; i++) {
                node1 = node1.next
            }
            return node1.element
        }

        LinkedList_oneWay.prototype.indexOf = function (element) {
            let index = 0
            let node1 = this.head
            while (index < this.length) {
                if (node1.element === element) {
                    return index
                }
                node1 = node1.next
                index++
            }
            return -1
        }

        LinkedList_oneWay.prototype.update = function (element, position) {
            if (position >= this.length) {
                return null
            }
            let node1 = this.head
            for (let i = 0; i < position; i++) {
                node1 = node1.next
            }
            node1.element = element
        }

        LinkedList_oneWay.prototype.removeAt = function (position) {
            if (position >= this.length) {
                return null
            }
            let node1 = this.head

            // 删除一项的原理：将(准备删除的节点的上一节点)的next指向(准备删除的节点的下一项)  跳过(准备删除的节点)
            for (let i = 0; i < position - 1; i++) {
                node1 = node1.next
            }
            let element = node1.next.element

            node1.next = node1.next.next
            this.length--

            return element
        }

        LinkedList_oneWay.prototype.remove = function (element) {
            let node1 = this.head
            let index = 0

            // 如果要删除的是第一个节点
            if (node1.element === element) {
                this.head = node1.next
                return index
            }
            while (node1 !== null) {
                index++  // 因为找的都是node1.next  如果找到了  则指定element应该是现在node1的下一项的element 所以应该提前index++
                // 找到下一节点的element 为 指定element 的节点
                if (node1.next.element === element) {
                    node1.next = node1.next.next
                    return index
                }
                node1 = node1.next
            }
            return -1
        }

        LinkedList_oneWay.prototype.isEmpty = function () {
            return this.head === null ? true : false
        }

        LinkedList_oneWay.prototype.size = function () {
            return this.length
        }

        LinkedList_oneWay.prototype.toString = function () {
            let node1 = this.head
            let arr = []
            // 遍历到最后的一项的下一项  不包括最后一项的下一项
            while (node1 !== null) {
                arr.push(node1.element)
                node1 = node1.next
            }
            return arr.join(',')
        }
    }

</script>

</html>